#include <iostream>
#include <fstream>
#include <stdio.h>
#include <list>
#include <vector>
#include <ctime>
#include <cstdlib>

using namespace std;

const int N = 10;
const int INFINITY = N;

#define M(i,j) m[(i)*N+(j)]

int * gen_graph(int n){
	srand(time(0));
	int * m = new int[n*n];
	for(int i = 0;i < n; i++){
		for(int j = 0; j < n; j++){
			if(i == j)
				M(i,j) = 0;
			else
				M(i,j) = INFINITY;
		}
	}
	for(int i = 0;i < n; i++){
		for(int j = 0; j < n / 5; j++){
			int dst = (i+rand()) % n;
			if(dst != i){
				int r = rand() % 5;
				r = (r == 0) ? 1 : INFINITY;
				M(i,dst) = M(dst,i) = r;
			}
		}
	}
	return m;
}

void out_graph(int * m,int n)
{
	FILE *f = fopen("graph.txt","w");
	for(int i = 0;i < n; i++){
		for(int j = i+1; j < n; j++)
		{
			if(M(i,j) != INFINITY)
				fprintf(f,"%d %d\n",i,j);
		}
	}
	fclose(f);
}

int main(){

	int * m = gen_graph(N);
	out_graph(m,N);
	vector<int> dist(N,INFINITY);
	dist[0] = 0;
	// calculate min-distance from vertex 0 to the other vertices
	list<int> curr_nodes;
	curr_nodes.push_back(0);
	list<int> new_nodes;
	while(1){
		// calculate new distance
		for(list<int>::iterator it = curr_nodes.begin();it!=curr_nodes.end();++it){
			int src = *it;
			for(int dst = 0; dst < N; dst++){
				if(dist[src] + M(src,dst) < dist[dst]){
					dist[dst] = dist[src] + M(src,dst);
					new_nodes.push_back(dst);
				}
			}
		}
		// exchange list
		if(new_nodes.size() == 0)
			break;
		curr_nodes.clear();
		curr_nodes.swap(new_nodes);
	}	

	// print the distance of vertex 0 to vertex 1,2,3,...10
	for(int i = 0; i < N; i++)
		printf("%d %d\n",i,dist[i]);

	return 0;
}
